# Definition for a binary tree node.
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right
root=TreeNode(1)
root.left=TreeNode(3)
root.left.right=TreeNode(2)

#中序遍历
def dfs(root,path):
    if root.left==None and root.right==None:
        path.append(root)
        return None
    if root.left!=None:
        dfs(root.left,path)
    path.append(root)
    if root.right!=None:
        dfs(root.right,path)
#根据中序遍历，来判断我们的二叉搜索树是否是正确的，如果不是，就去找那两个不对的点的位置
def recoverTree(root):
    """
    Do not return anything, modify root in-place instead.
    """
    path=[]
    dfs(root,path)
    if len(path)<=1:
        return root
    else:
        x,y=None,None
        left=path[0]
        for i in range(1,len(path)):
            if left.val>path[i].val:
                y=path[i]
                if not x:
                    x=left

            left=path[i]
        if x and y:
            x.val,y.val=y.val,x.val


class Solution(object):
    def recoverTree(self, root):
        #x和y用来记录两个错误了位置的结点
        x = None
        y = None
        #记录前一个结点
        pre = None
        tmp = None

        while root:
            #如果根节点的左孩子结点存在
            if root.left:
                #temp是根节点的左孩子结点
                tmp = root.left

                while tmp.right and tmp.right!=root:
                    tmp = tmp.right
                #右孩子结点不存在，把右孩子部分作为存储下一到达位置的结点
                if tmp.right is None:
                    tmp.right = root
                    root = root.left
                else:
                    if pre and pre.val>root.val:
                        y = root
                        if not x:
                            x = pre
                    pre = root
                    tmp.right = None
                    root = root.right
            else:
                if pre and pre.val>root.val:
                    y = root
                    if not x:
                        x = pre
                pre = root
                root = root.right
        if x and y:
            x.val,y.val = y.val,x.val

recoverTree(root)
